
Namespace std

    'keyType is the data type for storing, keyType2 is some wrap structure
    Public MustInherit Class mapbase(Of keyType, keyType2 As IComparable(Of keyType2), valueType, pairType As pairbase)
        Inherits xtree(Of pairType)

        Public MustInherit Class pairbase
            Inherits pair(Of keyType2, valueType)
            Implements IComparable(Of pairType)

#If RETIRED Then
            Protected Sub New(ByVal notAlloc As Boolean)
                MyBase.New(notAlloc)
            End Sub
#End If

            Protected MustOverride Sub setfirst(ByVal first As keyType) 'from keyType to keyType2
            Public MustOverride Shadows Function first() As keyType 'from keyType2 to keyType

            Protected Property internalfirst() As keyType2
                Get
                    Return MyBase.first
                End Get
                Set(ByVal value As keyType2)
                    MyBase.first = value
                End Set
            End Property

            Public Overloads Function CompareTo(ByVal that As pairType) As Int32 _
                                                                        Implements IComparable(Of pairType).CompareTo
                If that Is Nothing Then
                    Return compare(internalfirst(), CType(Nothing, keyType2))
                Else
                    Return compare(internalfirst(), that.internalfirst())
                End If
            End Function

            Protected Overridable Function generateInstance() As pairType
                Return alloc(Me)
            End Function

            Public NotOverridable Overrides Function Clone() As Object
                Dim obj As pairType = Nothing
                obj = generateInstance()
                obj.setdata(first(), second)
                Return obj
            End Function

            Protected Sub setdata(ByVal first As keyType, ByVal second As valueType)
                setfirst(first)
                copy(Me.second, second)
            End Sub
        End Class

        Public Shadows Function insert(ByVal key As keyType, ByVal value As valueType) As iterator
            Dim newNode As node = Nothing
            newNode = New node(make_pair(key, value))
            Return MyBase.insert(newNode)
        End Function

        Public Shadows Function insert(ByVal that As mapbase(Of keyType, keyType2, valueType, pairType)) As Boolean
            Dim it As mapbase(Of keyType, keyType2, valueType, pairType).iterator = Nothing
            it = that.begin()
            While it <> that.[end]()
                debugassert(insert((+it).first(), (+it).second) <> [end](), _
                            "insert " + Convert.ToString((+it).first()) + ", " + _
                            Convert.ToString((+it).second) + " returns false.")
                it += 1
            End While

            Return True
        End Function

        Public Overridable Overloads Function [erase](ByVal key As keyType) As Boolean
            Return MyBase.erase(make_pair(key, Nothing))
        End Function

        Default Public Property data(ByVal key As keyType) As valueType
            Get
                Dim rtn As iterator = Nothing
                rtn = find(key)
                If rtn = [end]() Then
                    rtn = insert(key, alloc(Of valueType)())
                End If
                Return (+rtn).second
            End Get
            Set(ByVal value As valueType)
                Dim rtn As iterator = Nothing
                rtn = find(key)
                If rtn = [end]() Then
                    rtn = insert(key, value)
                Else
                    copy((+rtn).second, value)
                End If
            End Set
        End Property

        Public Shadows Function find(ByVal key As keyType) As iterator
            Return MyBase.find(make_pair(key, Nothing))
        End Function

        'helper function to call internal signedpair/sortpair.make_pair
        Protected MustOverride Function make_pair(ByVal first As keyType, ByVal second As valueType) As pairType
    End Class

    Public Class sortmap(Of keyType As IComparable(Of keyType), valueType)
        Inherits mapbase(Of keyType, keyType, valueType, sortpair)

        Public Class sortpair
            Inherits pairbase

#If RETIRED Then
            Protected Sub New(ByVal notAlloc As Boolean)
                MyBase.New(notAlloc)
            End Sub
#End If

            Public Shared Shadows Function make_pair(ByVal first As keyType, ByVal second As valueType) As pairbase
                Dim rtn As sortpair = Nothing
#If RETIRED Then
                rtn = New sortpair(True)
#End If
                rtn = New sortpair()
                rtn.setdata(first, second)

                Return rtn
            End Function

            'do not need to copy here, setfirst should only be called by setdata / make_pair / insert
            Protected Overrides Sub setfirst(ByVal first As keyType)
                internalfirst() = first
            End Sub

            Public Overrides Function first() As keyType
                'get a copy here, should not be able to change first
                Dim rtn As keyType = Nothing
                copy(rtn, internalfirst())
                Return rtn
            End Function
        End Class

        Protected Overrides Function make_pair(ByVal first As keyType _
                                               , ByVal second As valueType) As sortmap(Of keyType, valueType).sortpair
            Return sortpair.make_pair(first, second)
        End Function
    End Class

    Public Class map(Of keyType As IComparable(Of keyType), valueType)
        Inherits mapbase(Of keyType, signednode(Of keyType), valueType, signedpair)

        Private _signingIndex As Int32

        Public Class signedpair
            Inherits pairbase

            Public Sub New(ByVal signingIndex As Int32)
                CType(Me, pair(Of signednode(Of keyType), valueType)).first = New signednode(Of keyType)(signingIndex)
            End Sub

            Public Shared Shadows Function make_pair(ByVal first As keyType, ByVal second As valueType, _
                                                     ByVal signingIndex As Int32) As signedpair
                Dim rtn As signedpair = Nothing
                rtn = New signedpair(signingIndex)
                rtn.setdata(first, second)

                Return rtn
            End Function

            Public Overrides Function first() As keyType
                Return internalfirst().data()
            End Function

            Protected Overrides Sub setfirst(ByVal first As keyType)
                'cannot avoid to copy here, signednode keep the logic
                internalfirst().data() = first
            End Sub

            Protected Overrides Function generateInstance() As signedpair
                Return New signedpair(internalfirst().signingIndex())
            End Function
        End Class

        Protected Overrides Function make_pair(ByVal first As keyType, ByVal second As valueType) As signedpair
            Return signedpair.make_pair(first, second, _signingIndex)
        End Function

        Public Overrides Function clone() As Object
            Dim rtn As map(Of keyType, valueType) = Nothing
            rtn = MyBase.clone()
            rtn._signingIndex = _signingIndex
            Return rtn
        End Function

        Public Sub New()
            MyBase.new()
            _signingIndex = rnd(0, _signing.maxSigningIndex, True)
        End Sub

        Private Class unittestInfo
            Public map As map(Of keyType, valueType) = Nothing
            Public keys As vector(Of keyType) = Nothing

            Public Sub New()
                map = New map(Of keyType, valueType)()
                keys = New vector(Of keyType)()
            End Sub
        End Class

        Private Class unittestActions
            Private Shared Sub parseParameter(ByVal obj As Object _
                                  , ByRef map As map(Of String, String) _
                                  , ByRef keys As vector(Of String))
                Dim info As map(Of String, String).unittestInfo = Nothing
                info = convertor.cast(Of map(Of String, String).unittestInfo)(obj)
                map = info.map
                keys = info.keys

                assert(Not map Is Nothing, "map is nothing.")
                assert(Not keys Is Nothing, "keys is nothing.")
            End Sub

            Public Shared Sub insert(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, m, keys)

                Dim k As String = Nothing
                k = createGUID()
                raiseError("insert " + k)
                assert(m.insert(k, createGUID()) <> m.end(), "m.insert(" + k + ", createGUID()) = m.end()")
                keys.push_back(k)
            End Sub

            Public Shared Sub [erase](ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, m, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    raiseError("remove " + keys(i))
                    assert(m.erase(keys(i)), "m.erase(" + keys(i) + ") returns false.")
                    keys.erase(i)
                End If
            End Sub

            Public Shared Sub find(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, m, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    raiseError("find " + keys(i))
                    assert(m.find(keys(i)) <> m.end(), "m.find(" + keys(i) + ") = m.end()")
                End If
            End Sub

            Public Shared Sub [get](ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, m, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    raiseError("show value of " + keys(i))
                    assert(Not isemptystring(m(keys(i))), "m(" + keys(i) + ") is an empty string, " + m(keys(i)))
                End If
            End Sub

            Public Shared Sub [set](ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, m, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    Dim s As String = Nothing
                    s = createGUID()
                    raiseError("set value of " + keys(i) + " to " + s)
                    m(keys(i)) = s
                    assert(m(keys(i)) = s, "m(" + keys(i) + ") <> " + s + ", now value is " + m(keys(i)))
                End If
            End Sub

            Public Shared Sub clone(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m, Nothing)

                Dim info As map(Of String, String).unittestInfo = Nothing
                info = convertor.cast(Of map(Of String, String).unittestInfo)(obj)
                Dim oldmap As map(Of String, String) = Nothing
                oldmap = info.map
                info.map = Nothing
                copy(info.map, m)
                assert(Not Object.ReferenceEquals(info.map, oldmap), "cannot clone to a new instance.")
                raiseError("clone a same instance with existing one.")
            End Sub

            Public Shared Sub clear(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, m, keys)

                m.clear()
                assert(m.size() = 0, "m.size()<>0 after clear.")
                keys.clear()
            End Sub
        End Class

        Public Shared Sub automaticalUnittest()
            Dim roundcount As Int64 = 10240
            If isreleasebuild() Then
                roundcount *= 20
            End If

            raiseError("********** map(of string,string) automatcial unittest **********" _
                       , errorHandle.errorType.application)

            Dim info As unittestInfo = Nothing
            info = New unittestInfo()
            randomrun.invoke(roundcount, info _
                             , New randomrun.info(0.32, AddressOf unittestActions.insert) _
                             , New randomrun.info(0.15, AddressOf unittestActions.set) _
                             , New randomrun.info(0.15, AddressOf unittestActions.get) _
                             , New randomrun.info(0.2, AddressOf unittestActions.erase) _
                             , New randomrun.info(0.11, AddressOf unittestActions.find) _
                             , New randomrun.info(0.01, AddressOf unittestActions.clone) _
                             , New randomrun.info(0.06, AddressOf unittestActions.clear))
            While Not info.map.empty()
                unittestActions.erase(info)
            End While

            raiseError("***************** finish automatical unittest ******************" _
                       , errorHandle.errorType.application)
        End Sub

        Private Class perftestActions
            Private Shared Sub parseParameter(ByVal obj As Object, ByRef m As map(Of String, String))
                m = convertor.cast(Of map(Of String, String))(obj)
                assert(Not m Is Nothing, "m is nothing.")
            End Sub

            Public Shared Sub insert(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("insert")
                m.insert(createGUID(), createGUID())
            End Sub

            Public Shared Sub [set](ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("set")
                m(createGUID()) = createGUID()
            End Sub

            Public Shared Sub [get](ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("get result " + m(createGUID()))
            End Sub

            Public Shared Sub [erase](ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("erase")
                m.erase(createGUID())
            End Sub

            Public Shared Sub find(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("find")
                m.find(createGUID())
            End Sub

            Public Shared Sub clone(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("clone")
                Dim m2 As map(Of String, String) = Nothing
                copy(m2, m)
            End Sub

            Public Shared Sub clear(ByVal obj As Object)
                Dim m As map(Of String, String) = Nothing
                parseParameter(obj, m)

                raiseError("clear")
                m.clear()
            End Sub
        End Class

        Public Shared Sub performanceTest()
            Dim roundcount As Int64 = 102400
            If isreleasebuild() Then
                roundcount *= 20
            End If

            raiseError("********** map(of string,string) automatical perfTest **********" _
                       , errorHandle.errorType.application)

            Dim m As map(Of String, String) = Nothing
            m = New map(Of String, String)()
            randomrun.invoke(roundcount, m _
                             , New randomrun.info(0.32, AddressOf perftestActions.insert) _
                             , New randomrun.info(0.15, AddressOf perftestActions.set) _
                             , New randomrun.info(0.15, AddressOf perftestActions.get) _
                             , New randomrun.info(0.2, AddressOf perftestActions.erase) _
                             , New randomrun.info(0.11, AddressOf perftestActions.find) _
                             , New randomrun.info(0.01, AddressOf perftestActions.clone) _
                             , New randomrun.info(0.06, AddressOf perftestActions.clear))

            raiseError("***************** finish automatical perftest ******************" _
                       , errorHandle.errorType.application)
        End Sub
    End Class
End Namespace

